import collections


class Solution:
    # 将每一条公交路线（而不是每一个车站）看成图中的一个点，如果两条
    # 公交路线有交集，那么它们在图中对应的点之间就有一条边。
    # 起点站 S 和终点站 T 也分别是图中的一个点，如果一条公交路线包含
    # 了 S 或 T，那么也需要和 S 或 T 对应的点连一条边。
    # 用广度优先搜索来找出最短路径。
    def numBusesToDestination(self, routes, source: int, target: int) -> int:
        if source == target: return 0
        # 1. 构建图结构
        graph = collections.defaultdict(set)  # enables default behaviour
        routes = list(map(set, routes))  # a list of sets
        for i in range(len(routes)):
            for j in range(i+1, len(routes)):
                if len(routes[i].intersection(routes[j])) > 0:  # 若有交集则为邻
                    # i, j 为路线在图上的编号
                    graph[i].add(j)  # graph[i] is a set
                    graph[j].add(i)  # can go in both directions
        # If a node has no neighbour, then the graph gives you an empty set
        
        # 2. 起点与终点设置 => 关联到图上
        visited, dest = set(), set()            # dest 为目的地 (destination)
        for i, route in enumerate(routes):
            if source in route: visited.add(i)  # 找到初始节点并设置为 visited
            if target in route: dest.add(i)     # 找到目标节点并设置为 dest
        
        # 3. BFS (使用队列数据结构支持)
        queue = [(i, 1) for i in visited]  # 初始队列只包含 visited 节点
        for i, numBuses in queue:
            if i in dest: return numBuses  # node i is in dest
            for j in graph[i]:  # 遍历 i 的每个邻居 j
                if j not in visited:
                    visited.add(j)  # node j 设为`被访问过`
                    queue.append((j, numBuses+1))  # node j 放入队列
        return -1  # 没有到达目的地


if __name__ == "__main__":
    routes = [[1,2,7],[3,6,7]]
    soln = Solution()
    print(soln.numBusesToDestination(routes, 1, 6))
